/*
 * @lc app=leetcode.cn id=63 lang=javascript
 *
 * [63] 不同路径 II
 */

// @lc code=start
/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function (obstacleGrid) {
  const m = obstacleGrid.length;
  const n = obstacleGrid[0].length;
  const curMax = Array.from({ length: m }, () => new Array(n).fill(0));
  //第一行或列遇到障碍就不走下去
  for (let x = 0; x < m; x++) {
    if (obstacleGrid[x][0] == 0) curMax[x][0] = 1;
    else break;
  }
  for (let x = 0; x < n; x++) {
    if (obstacleGrid[0][x] === 0) curMax[0][x] = 1;
    else break;
  }
  // 中间情况，遇到障碍，路径数置0
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (obstacleGrid[i][j]) curMax[i][j] = 0;
      else {
        curMax[i][j] = curMax[i - 1][j] + curMax[i][j - 1];
      }
    }
  }
  return curMax[m - 1][n - 1];
};
// @lc code=end
